package com.example.javamaday.graph;

/**
 * 判断图中是否有环
 */
public class DirectedCycle {

    // 索引代表顶点，值表示顶点是否被搜索过
    private boolean[] marked;

    // 记录图中是否有环
    private boolean hasCycle;

    // 索引代表顶点，使用栈的思想，记录当前顶点没有已经处于正在搜索的有向路径上。
    private boolean[] onStack;

    public DirectedCycle(Digraph digraph) {
        marked = new boolean[digraph.V()];
        onStack = new boolean[digraph.V()];
        this.hasCycle = false;
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]) {
                dfs(digraph, v);
            }
        }
    }

    private void dfs(Digraph digraph, int v) {
        marked[v] = true;
        onStack[v] = true;
        for (Integer w : digraph.adj(v)) {
            if (!marked[w]) {
                dfs(digraph, w);
            }
            if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public static void main(String[] args) {
        Digraph digraph = new Digraph(5);
        digraph.addEdge(3, 0);
        digraph.addEdge(0, 2);
        digraph.addEdge(2, 1);
        digraph.addEdge(1, 0);
        digraph.addEdge(1, 4);
        DirectedCycle directedCycle = new DirectedCycle(digraph);
        boolean isHasCycle = directedCycle.hasCycle();
        System.out.println("当前图是否存在环：" + isHasCycle);
    }

}
